home *** CD-ROM | disk | FTP | other *** search
/ Group 42-Sells Out! - The Information Archive / Group 42 Sells Out (Group 42) (1996).iso / crypto / 2xdesfou.txt next >
Text File  |  1995-11-30  |  7KB  |  166 lines
  1.                        Nx2 DES Found Weak
  2.  
  3.  Summary
  4.  
  5.  Any Nx2 DES system succumbs to meet-in-the-middle attack at a
  6.  cost only N times that of normal DES, and is probably not worth
  7.  using.  If we assume that DES would fall with 2^55 cipherings
  8.  (on average), then the 4x2+ DES system which I previously
  9.  recommended would require only 2^57 cipherings.  Such an attack,
  10.  however, might require substantially more storage and might be
  11.  more difficult to mechanize and slower in operation than an attack
  12.  on normal DES.
  13.  
  14.  Nx3 DES systems seem not to be affected by this attack, but they
  15.  are also not faster than triple-DES (1x3 DES), which was the main
  16.  reason for recommending Nx2 DES over triple-DES.  On the other
  17.  hand, Nx3 DES systems apparently would provide added strength
  18.  against dictionary attacks; such attacks might be possible against
  19.  ASCII plaintext when ciphered in small 8-byte blocks.
  20.  
  21.  
  22.  Double-DES
  23.  
  24.  A 1x2 DES construct (double-DES) is something like this:
  25.  
  26.              A
  27.              v
  28.       k1 -> DES1
  29.              v
  30.              B
  31.              v
  32.       k2 -> DES2
  33.              v
  34.              C
  35.  
  36.  Each single capital letter represents an 8-byte DES block.
  37.  
  38.  
  39.  Meet-In-The-Middle Attack on 1x2 DES (double-DES)
  40.  
  41.       [ This is probably similar to:
  42.  
  43.         Merkle, R. and M. Hellman.  1981.  On the security of
  44.         multiple encryption.  Comm. ACM 27(4): 465.
  45.  
  46.       which I have not seen.  This analysis resulted from trying to
  47.       understand the comments on NxM DES made by email from Eli
  48.       Biham, which led me to:
  49.  
  50.         Davies, D. and W. Price.  1984.  Security for Computer
  51.         Networks.  Wiley.  75.
  52.  
  53.       and the attack on double-DES.  Obviously I did not expect
  54.       that attack to work on Nx2 DES, or I would have skipped Nx2
  55.       entirely. ]
  56.  
  57.  First we need some known-plaintext (A) and its associated ciphertext
  58.  (C).  Now we encipher A with every possible random key k1 and save
  59.  the results.  Then we decipher C with random keys k2, eventually
  60.  finding a match to the enciphered data.
  61.  
  62.  There are many possible pairs of keys (k1, k2) which will produce
  63.  matching B's.  Since there are 112 key bits (k1, k2), and we match
  64.  64 bits each time, there should be about 112 - 64 or 48 bits of
  65.  freedom (that is, 2^48 possibilities) to be resolved with one or
  66.  two more known-plaintext blocks.
  67.  
  68.  We can guarantee to find the correct key pair if we try every
  69.  possible key for k1 and also every possible key for k2; this is
  70.  only twice the effort of a full DES key search, and we need
  71.  only search half that, on average.  (In practice, we would do
  72.  some k1's and then some k2's, repeated until success occurred.)
  73.  
  74.  However, we should note that this technique may require the
  75.  intermediate storage of 2^56 results.  This would be over 2^59
  76.  bytes of store, and this amount of storage and lookup is not
  77.  nearly as easy or fast as the on-chip ciphering-and-compare
  78.  solution for DES.  Still, the result is not comforting.
  79.  
  80.  
  81.  A 2x2 DES construct is something like this:
  82.  
  83.              A             B
  84.              v             v
  85.       k1 -> DES1    k2 -> DES2
  86.              v             v
  87.              C             D
  88.               Exchange Half
  89.              E             F
  90.              v             v
  91.       k3 -> DES3    k4 -> DES4
  92.              v             v
  93.              G             H
  94.  
  95.  
  96.  
  97.  Meet-In-The-Middle Attack on 2x2 DES
  98.  
  99.  Suppose we first try the 2x1 approach:  With one known-plaintext
  100.  block, we can search two keys (say k1 and k2) until a match
  101.  is found for the center block.  Then we can validate that match
  102.  with additional known-plaintext blocks.  (Since there is only a
  103.  32-bit match-check and a 112-bit keyspace, there will be
  104.  112 - 32 or 80 bits of freedom to resolve at about 32 bits per
  105.  known-plaintext pair, so we would want to check a minimum of 3 or
  106.  4 other known-plaintexts.  The cost of the subsequent cipherings
  107.  and comparisons would be relatively insignificant, however.)
  108.  
  109.  We can guarantee that the two keys will be found by searching all
  110.  possible k1 and k2.  This is only twice the normal DES keyspace,
  111.  and we only need search half of that, on average.  And we can do
  112.  this again for the other two keys at a similar cost.  Again, the
  113.  attack hardware will be considerably more awkward than any simple
  114.  search for a DES key which matches a given ciphertext value, but
  115.  the total number of DES cipherings will be about twice the DES
  116.  keyspace, on average.
  117.  
  118.  
  119.  Nx2 DES Falls
  120.  
  121.  Similar arguments lead to the conclusion that, for any N, Nx2 DES
  122.  must be generally comparable in strength to DES itself.  This means
  123.  that the larger block has not helped strength much in any Nx2 DES
  124.  system, despite the fact that every ciphertext bit is demonstrably
  125.  a function of every plaintext bit in the large block as well as
  126.  every bit in all the separate DES keys.  Note that the form of the
  127.  inter-stage permutation has absolutely no effect on this attack
  128.  or overall strength, despite the fact that a great deal has been
  129.  written about designing S-P permutations.
  130.  
  131.  The meet-in-the-middle attack seems not to apply to Nx3 DES.
  132.  
  133.  
  134.  Dictionary Attacks
  135.  
  136.  Normally we define "strength" as the *minimum* effort expected to
  137.  "break" a cipher, when taken over *all possible attacks*.  Working
  138.  out the extent of "all possible attacks" is a major part of the
  139.  effort in cryptography.
  140.  
  141.  With respect to DES, most of the current attacks have considered
  142.  the relatively-small 56-bit keyspace.  But I am also concerned
  143.  by the relatively-small 8-byte block size.
  144.  
  145.  Consider an 8-byte block of ASCII text:  Modern data-compression
  146.  programs typically compress such data by 60 percent.  This means
  147.  that we typically have less than 26 bits or so of "uniqueness" in
  148.  the various blocks.  Rigidly-formatted business documents, letters,
  149.  or forms would be even less unique, and, thus, even more attackable.
  150.  
  151.  To the extent that a substantial amount of known-plaintext could
  152.  be acquired (or possibly even inferred), a dictionary attack
  153.  becomes possible.  For this reason, if a change is to be made,
  154.  then I would like to see a block size at least four times that
  155.  now used.  This would be a reasonable approach with a 4x3+ DES
  156.  system, which would be comparable in throughput to a 1x3 DES
  157.  system, but, alas, not faster.
  158.  
  159.  
  160.  Conclusion
  161.  
  162.  A two-stage or Nx2 DES construction is probably not worth using.
  163.  
  164.  
  165.  
  166.